from typing import List
from collections import defaultdict
from functools import lru_cache


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        mem = defaultdict(list)
        if any([i not in set("".join(wordDict)) for i in s]):
            return []
        for word in wordDict:
            mem[word[0]].append(word)
        print(mem)

        # start = 0
        res = []

        @lru_cache
        def dfs(start, l):
            # if start > len(s):
            #     return
            print(start,)
            if start == len(s):
                res.append(l)
                print("l=", l)
                return
            elif start > len(s):
                return
            print(start, l)
            for word in mem.get(s[start], []):
                if not s[start:].startswith(word):
                    continue
                if not l:
                    dfs(start + len(word), word)
                else:
                    dfs(start + len(word), l + " " + word)

        dfs(0, "")
        return res


if __name__ == "__main__":
    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    wordDict = [
        "a",
        "aa",
        "aaa",
        "aaaa",
        "aaaaa",
        "aaaaaa",
        "aaaaaaa",
        "aaaaaaaa",
        "aaaaaaaaa",
        "aaaaaaaaaa",
    ]
    # s = "pineapplepenapple"
    # wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
    res = Solution().wordBreak(s, wordDict)
    print("res=", res)
